package com.algorithm.learning.sort;

import java.util.Arrays;

/**
 * @program: algorithm-learning
 * @description: 对于归并排序来说，排序的思想是分而治之，
 *  将一个无序数组，拆分成若干个子数组，然后对子数组进行排序，这样子数组有序的情况下，在归并有序数组，从而达到整体有序
 * @author: YuKai Fan
 * @create: 2024/8/18 16:13
 **/
public class 归并排序 {

    public void merge(int[] nums1, int m, int[] nums2, int n) {
        if (n == 0) {
            return;
        }
        if (m == 0) {
            for (int i = 0; i < nums2.length; i++) {
                nums1[i] = nums2[i];
            }
            return;
        }
        int[] temp = new int[m + n];
        int i = 0;
        int p1 = 0;
        int p2 = 0;
        // 这里其实不用关心nums1后面有n个0的情况
        // 因为这里题目给的m的值，只是不包含后面位0的值
        /*
        例如 nums1=[1,2,3,0,0,0]，m=3，也就是说，这里的m值包含后续不为0的长度，
        而在因为下面的while循环中，p1永远小于m，所以根本不可能遍历到后续的0，要想遍历到0，那么m肯定是要为6才可以，
        所以不用担心
         */
        while (p1 < m && p2 < n) {
            temp[i++] = nums1[p1] <= nums2[p2] ? nums1[p1++] : nums2[p2++];
        }
        while (p1 < m) {
            temp[i++] = nums1[p1++];
        }
        while (p2 < n) {
            temp[i++] = nums2[p2++];
        }
        for (int j = 0; j < temp.length; j++) {
            nums1[j] = temp[j];
        }
    }

    public static void main(String[] args) {
//        int[] nums = new int[]{6, 7, 8, 9, 10,1, 2, 3, 4, 5};
//        new 归并排序().mergeSort(nums);
//        System.out.println(Arrays.toString(nums));
        int[] nums1 = new int[]{1,7,8,0,0,0};
        int[] nums2 = new int[]{2,5,6};
        new 归并排序().merge(nums1, 3, nums2, 3);
        System.out.println(Arrays.toString(nums1));
    }

    /**
     * 归并排序的步骤如下：
     *
     * 1、首先需要将整个数组拆分，拆分到不可拆分为止，那不可拆分的情况就是数组中只有一个元素。
     *      要注意为什么要拆分到一个元素，因为原数组其实是无序的，而归并排序一定是在多个有序数组的基础上才能使用
     *      所以下面代码一直在做递归拆分的目的实际上是进行排序，一直递归到只有一个元素，那一个元素肯定是有序的，这样就可以向上合并成一个有序数组
     *
     * 2、当递归拆分成只有一个元素的时候，那么此时就可以进行合并，合并步骤如下：
     *      2.1、首先归并排序是需要申请临时数组空间
     *          这里要注意，临时数组空间的大小是怎么定的，其实也很简单，我们知道最终要合并的数组区间一定是[left, right]，所以临时数组大小就是right - left + 1
     *      2.2、其次定义两个变量指针，p1指向left，p2指向mid + 1，这样就是在分析归并排序时，需要从头开始比较两个数组的大小
     *      2.3、注意边界判断，如果p1<=mid && p2<=right 表示p1和p2都没有越界，此时哪个小，就把对应的数组元素赋值到临时数组对应的位置
     *          即temp[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++]，这里每次执行完，p1或p2都会+1，进行右移判断
     *      2.4、根据归并排序的原理，肯定会存在左右两个数组一定有一个数组先移动到边界，那么剩下的一个数组已经是有序了，直接将剩下的数组赋值给临时数组即可
     *          也就是说：while (p1 <= mid) 或者 while (p2 <= right) 只会执行一个
     */
    public void mergeSort(int[] arr) {
        mergeSort(arr, 0, arr.length - 1);
    }

    /**
     * 对数组nums在区间[left, right] 内进行归并排序，
     *
     * 可以采用递归的方式归并，那么递归打破的条件，就是left==right,此时只有一个元素
     * @param arr
     * @param left
     * @param right
     */
    private void mergeSort(int[] arr, int left, int right) {
        if (left == right) {
            return;
        }
        int mid = left + (right - left) / 2;
        // 经过下面两个步骤，可以得到两个区间的数组
        // [left, mid]
        mergeSort(arr, left, mid);
        // [mid + 1, right]
        mergeSort(arr, mid + 1, right);
        // 下面就开始合并两个数组
        mergeToArray(arr, left, mid, right);
    }

    /**
     * 这里的合并需要解释
     * @param arr 整个数组
     * @param left
     * @param mid
     * @param right
     */
    private void mergeToArray(int[] arr, int left, int mid, int right) {
        // right -left + 1，就是原数组的长度，相当于开辟一个与原数组等长的临时数组
        int[] temp = new int[right - left + 1];
        int i = 0;
        // 这里p1指向left 位置
        int p1 = left;
        // p2 指向mid + 1位置，也就是开始进行比较合并
        int p2 = mid + 1;
        // 开始合并
        // 这是没有越界的场景
        // 当p1没有越界，p2没有越界，比较大小，哪个小，哪个就放到临时数组中
        while (p1 <= mid && p2 <= right) {
            temp[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
        }
        // 下面需要处理其中一个越界的情况
        // 如果p1<=mid，说明左边的数组没有越界，那么左边的数组剩下的元素已经排好序，且大于其他元素,那么直接放入temp即可
        while (p1 <= mid) {
            temp[i++] = arr[p1++];
        }
        // 对于p2<=right, 说明右边的数组没有越界，那么右边的数组剩下的元素已经排好序，且大于其他元素,那么直接放入temp即可
        while (p2 <= right) {
            temp[i++] = arr[p2++];
        }
        for (int j = 0; j < temp.length; j++) {
            arr[left + j] = temp[j];
        }
    }
}
